// https://leetcode.cn/problems/inorder-successor-in-bst/submissions/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

// 法一：中序遍历
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode* pre = NULL;
        stack<TreeNode*> s;
        while (!s.empty() || root) {
            while (root) {
                s.push(root);
                root = root->left;
            }
            root = s.top();
            s.pop();
            if (pre == p) return root;
            pre = root;
            root = root->right;
        }
        return NULL;
    }
};

// 法二：
// 中序后继是节点值大于 p 的节点值的所有节点中节点值最小的一个节点
// 如果节点 p 的右子树不为空，则节点 p 的中序后继在其右子树中，在其右子树中定位到最左边的节点，即为节点 p 的中序后继。
// 如果节点 p 的右子树为空，则需要从根节点开始遍历寻找节点 p 的祖先节点。
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode* successor = NULL;
        if (p->right) {
            successor = p->right;
            while (successor->left) {
                successor = successor->left;
            }
            return successor;
        }
        TreeNode* tmp = root;
        while (tmp != p) {
            if (tmp->val > p->val) {
                successor = tmp;
                tmp = tmp->left;
            } else {
                tmp = tmp->right;
            }
        }
        return successor;
    }
};